// bzoj2820
// 题意：给定n, m(<=10000000)，求x<=n, y<=m, gcd(x, y)=prime的对数。
//
// 题解：首先还是令
//        f(i) = (gcd(x, y) = i, x<=n, y<=m)的对数，
//        F(i) = (i | gcd(x, y))的对数。
//       那么答案就是sigma(f(p))。
//       直接求肯定TLE.
//		  详细见blog吧，在这儿打公式太蛋疼。
//
//
// 统计：3368ms, 1h, 1a
//
#include <cstdio>
#include <algorithm>

int const maxn = 10000005;
int mo[maxn], g[maxn], sumg[maxn]; // g(T) = sigma(μ(T/p)) where p is a prime and p | T
bool not_prime[maxn];
int prime[maxn];
int tot;

void init_mobius(int n = maxn)
{
	mo[1] = 1;
	for (int i = 2; i < n; i++) {
		if (!not_prime[i]) prime[++tot] = i, mo[i] = -1, g[i] = 1;
		for (int j = 1; prime[j] * i < n; j++) {
			not_prime[prime[j] * i] = true;
			if (i % prime[j] == 0) {
				mo[prime[j] * i] = 0;
				g[prime[j] * i] = mo[i];
				break;
			}
			mo[prime[j] * i] = -mo[i];
			g[prime[j] * i] = mo[i] - g[i];
		}
	}
	for (int i = 1; i < n; i++) sumg[i] = sumg[i - 1] + g[i];
}

long long inverse(int n, int m)
{
	if (n > m) std::swap(n, m);
	long long ans = 0; int pos = 1;
	for (int i = pos; i <= n; i = pos + 1) {
		pos = std::min(n / (n/i), m / (m/i));
		ans += (long long)(sumg[pos] - sumg[i - 1]) * (n/i) * (m/i);
	}
	return ans;
}

int main()
{
	int T;
	std::scanf("%d", &T);
	init_mobius();
	while (T--) {
		int n, m;
		std::scanf("%d %d", &n, &m);
		std::printf("%lld\n", inverse(n, m));
	}
}

